#ifndef ORDEREDARRAY_H
#define ORDEREDARRAY_H

#include <Globals.h>
#include <MonitorDriver.h>

/**
  This array is insertion sorted - it always remains in a sorted state (between
  calls).
*/
template <class T, u32int N>
class OrderedArray
{
public:
  /**
    Constructor
  **/
  OrderedArray()
  {
    for (int i = 0; i < N; i++)
    {
      array[i] = NULL;
    }
    size = 0;
    lessThan = ( bool (*)(T, T) ) NULL;
  }

  ~OrderedArray() {}
  
  /**
    Sets the predicate to use for comparisons. The predicate should return
    true if the first argument is less than the second argument.
  **/
  void setPredicate( bool (*pred)(T, T) )
  {
    lessThan = pred;
  }
  
  /**
    Inserts item into the array at the correct place (sorted).
  **/
  void insert(T item)
  {
    ASSERT(lessThan);
    ASSERT(size+1 < N);
    u32int iterator = 0;
    while (iterator < size && lessThan(array[iterator], item))
    {
      iterator++;
    }
    if (iterator == size) // just add at end of array
    {
      array[size++] = item;
    }
    else
    {
      T tmp = array[iterator];
      array[iterator] = item;
      while (iterator < size)
      {
        iterator++;
        T tmp2 = array[iterator];
        array[iterator] = tmp;
        tmp = tmp2;
      }
      size++;
    }
  }
  
  /**
    Looks up the item at location idx.
  **/
  T getItem(u32int idx)
  {
    return array[idx];
  }
  
  /**
    Deletes the item at location idx from the array.
  **/
  void remove(u32int idx)
  {
    while (idx < size)
    {
      array[idx] = array[idx+1];
      idx++;
    }
    size--;
  }
  
  /**
    Debug helper function.
  **/
  void dump()
  {
    monitor.write("Dumping OrderedArray ");
    monitor.writeHex((u32int)this);
    for(int i = 0; i < size; i++)
    {
      monitor.write("\n\t");
      monitor.writeHex((u32int)array[i]);
    }
    monitor.write("\n");
  }

  u32int getSize()
  {
    return size;
  }

private:
  T array[N];
  u32int size;
  bool (*lessThan)(T, T);

};

#endif
